With the increased demand for security and safety, video-based surveillance systems are being employed in a variety of rural and urban locations. A vast amount of video footage, for example, can be collected and analyzed for traffic violations, accidents, crime, terrorism, vandalism, and other suspicious activities. Because manual analysis of such large volumes of data is prohibitively costly, a pressing need exists for developing effective software tools that can aid in the automatic or semi-automatic interpretation and analysis of video data for surveillance, law enforcement, and traffic control and management.
Video-based anomaly detection refers to the problem of identifying patterns in data that do not conform to expected behavior, and which may warrant special attention or action. The detection of anomalies in a transportation domain can include, for example, traffic violations, unsafe driver/pedestrian behavior, accidents, etc. FIGS. 1-2 illustrate pictorial views of exemplary transportation related anomalies captured from, for example, video monitoring cameras. In the scenario depicted in FIG. 1, unattended baggage 100 is shown and identified by a circle. In the example shown in FIG. 2, a vehicle is depicted approaching a pedestrian 130. Both the vehicle and pedestrian 130 are shown surrounded by a circle.
A number of anomalies can be generated by a typical trajectory/behavior of a single object and collective anomalies can be caused by joint observation of the objects. For example, in the area of transportation, accidents at traffic intersections are indeed based on joint and not just individual object behavior. Also, it is possible that the individual object behaviors are not anomalous when studied in isolation, but in combination produce an anomalous event. For example, a vehicle that comes to a stop at a pedestrian crossing before proceeding is a result of the car colliding with, or coming in very close proximity with the crossing pedestrian.
Several approaches have been proposed to detect the traffic-related anomalies based on an object tracking technique. In one prior art approach, nominal vehicle paths or trajectories can be derived and deviations thereof can be searched in a live traffic video data. The vehicle is tracked and its path is compared against nominal classes during a test or evaluation phase. A statistically significant deviation from all classes indicates an anomalous path. A problem associated with such approach is that an abnormal pattern in realistic scenarios involving multiple object trajectories in the presence of occlusions, clutter, and other background noise are not detected. Also, the algorithms are not computationally simple enough to detect the anomalies in quasi-real-time.
Another approach involves the use of a sparse reconstruction model to solve the classification problem and subsequently for anomaly detection. For example, a normal and/or usual event in a video footage can be extracted and categorized into a set of nominal event classes in a training step. The categorization is based on a set of n-dimensional feature vectors extracted from the video data and can be performed manually or automatically. The parametric representations of vehicle trajectories can be chosen as features and any new nominal sample can be explained by a linear combination of samples within one of the nominal classes.
The training samples from the i-th class can be arranged as columns of a matrix Aiεn×T. A dictionary Aεn×KT with respect to the training samples from all K classes can then be formed as follows: A=[A1, A2, . . . , AK]. A test image yεn from a similar class is conjectured to approximately lie in a linear span of those training samples for given sufficient training samples from the m-th trajectory class. Any input trajectory feature vector may hence be represented by a sparse linear combination of the set of all training trajectory samples as shown below in equation (1):
                    y        =                              A            ⁢                                                  ⁢            α                    =                                    [                                                A                  1                                ,                                  A                  2                                ,                …                ⁢                                                                  ,                                  A                  K                                            ]                        ⁡                          [                                                                                          α                      1                                                                                                                                  α                      2                                                                                                            ⋮                                                                                                              α                      K                                                                                  ]                                                          (        1        )            where each αiεT. Typically for a given trajectory y, only one of the ai's is active (corresponding to the class/event that y is generated from), thus the coefficient vector αεKT is modeled as being sparse and is recovered by solving the following optimization problem:
                              α          ^                =                                                                              argmin                                                                              α                                                      ⁢                                                          α                                            1                        ⁢                                                  ⁢            subject            ⁢                                                  ⁢            to            ⁢                                                  ⁢                                                                            y                  -                                      A                    ⁢                                                                                  ⁢                    α                                                                              2                                <          ɛ                                    (        2        )            where the objective is to minimize the number of non-zero elements in a. It is well-known from the compressed sensing literature that utilizing the I0 norm leads to a NP-hard (non-deterministic polynomial-time hard) problem. Thus, the I1 norm can be employed as an effective approximation. A residual error between the test trajectory and each class behavior pattern can be computed as shown in equation (3) to determine a class to which the test trajectory belongs:ri(y)=∥y−Ai{circumflex over (α)}i∥2 i=1,2, . . . ,K  (3)
If anomalies have been predefined into their own class, then the classification task also accomplishes anomaly detection. Alternatively, if all training classes correspond to only normal events, then anomalies can be identified via outlier detection. To this end, an index of sparsity can be defined and utilized to measure the sparsity of the reconstructed a:
                              SCI          ⁡                      (            α            )                          =                                                            K                ·                                                      max                    i                                    ⁢                                                                                                                                                                  δ                            i                                                    ⁡                                                      (                            α                            )                                                                                                                      1                                        /                                                                                          α                                                                    1                                                                                  -              1                                      K              -              1                                ∈                      [                          0              ,              1                        ]                                              (        4        )            where δi(α):T→T the characteristic function that selects the coefficients ai with respect to the i-th class. The normal samples are likely to exhibit a high level of sparsity, and conversely, anomalous samples likely produce a low sparsity index. A threshold on SCI(a) determines whether or not the sample is anomalous. Such sparsity based framework for classification and anomaly detection is robust against various distortions, notably occlusion and is robust with respect to the particular features chosen, provided the sparse representation is computed correctly.
However, such an approach does not take into account joint anomalies involving multiple objects and does not capture the interactions required to detect these types of multi-object anomalies. To address this issue, a joint sparsity model can be employed to detect anomalies involving co-occurrence of two or more events. The joint sparsity model solves for the sparse coefficients via the optimization problem. An example of the optimization problem and the joint sparsity model is discussed in U.S. patent application Ser. No. 13/476,239, entitled “Method and System for Automatically Detecting Multi-Object Anomalies Utilizing Joint Sparse Reconstruction Model,” which is is incorporated herein by reference in its entirety. The optimization problem can be expressed as, for example:minimize ∥J(H∘S)∥row,0 subject to ∥Y−AS∥F<ε  (5)
This anomaly detection technique based on the sparsity model is particularly robust against various distortions, notably occlusion, and identifies anomalies with high accuracy rates. The model, however, relies upon a certain structure wherein there exists a rigid object correspondence between the training dictionary A and the test trajectories Y. Furthermore, one needs to know whether a given anomaly involves a single object or P>1 objects. In the case of the latter, it is necessary to know how many objects are involved in an event (i.e., what is P) in order to trigger the appropriate training dictionary, constructed separately for each value of P.
In real world scenarios, events are sometimes difficult to be grouped into either single- or multi-object events even as trajectory data corresponding to each object (whether observed independently or jointly at the same time instant) becomes available in real time. This is feasible in a structured scenario such as a stop sign or a traffic intersection, where events commonly involve a certain number of objects. However, the approach becomes unrealistic in more general transportation scenarios (e.g., a busy airport or parking lot) where object motion is unrestricted and does not exhibit repeated patterns making it difficult to form associations of objects in training videos to those in the test videos. Furthermore, equation (2) and its extension for multi-object anomaly detection are expensive from the viewpoint of computation and partially stems from the fact that they correspond to a non-convex optimization problem.
FIG. 3 represents an example wherein the joint sparsity model may fail if the order of test trajectories is different from that of the training trajectories. Another example of a video frame with crowded unstructured traffic patterns is shown in FIG. 4. It is not known if the trajectory of the pedestrian should be analyzed as a single event or joint event. In summary, previous formulations of the sparsity model and the joint sparsity model are suitable for solving only the structured scenario where it is feasible to readily determine the number and sequence of objects involved in the events.
Based on the foregoing, it is believed that a need exists for an improved method and system for detecting single- and multi-object anomalies in an unstructured scenario where the number and sequence of objects in an event are not known or easily obtainable. The proposed method and system is based on a low rank sparsity prior model, as will be described in greater detailed herein.